/*
 * LRUCache11 - a templated C++11 based LRU cache class that allows
 * specification of
 * key, value and optionally the map container type (defaults to
 * std::unordered_map)
 * By using the std::map and a linked list of keys it allows O(1) insert, delete
 * and
 * refresh operations.
 *
 * This is a header-only library and all you need is the LRUCache11.hpp file
 *
 * Github: https://github.com/mohaps/lrucache11
 *
 * This is a follow-up to the LRUCache project -
 * https://github.com/mohaps/lrucache
 *
 * Copyright (c) 2012-22 SAURAV MOHAPATRA <mohaps@gmail.com>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
#pragma once
#include <algorithm>
#include <cstdint>
#include <list>
#include <mutex>
#include <stdexcept>
#include <thread>
#include <unordered_map>

namespace lru11 {

    /*
     * a noop lockable concept that can be used in place of std::mutex
     */
    class NullLock {
    public:

        void lock() {
        }

        void unlock() {
        }

        bool try_lock() {
            return true;
        }
    };

    /**
     * error raised when a key not in cache is passed to get()
     */
    class KeyNotFound : public std::invalid_argument {
    public:

        KeyNotFound() : std::invalid_argument("key_not_found") {
        }
    };

    template <typename K, typename V>
    struct KeyValuePair {
    public:
        K key;
        V value;

        KeyValuePair(const K& k, const V& v) : key(k), value(v) {
        }
    };

    /**
     *	The LRU Cache class templated by
     *		Key - key type
     *		Value - value type
     *		MapType - an associative container like std::unordered_map
     *		LockType - a lock type derived from the Lock class (default:
     *NullLock = no synchronization)
     *
     *	The default NullLock based template is not thread-safe, however passing
     *Lock=std::mutex will make it
     *	thread-safe
     */
    template <class Key, class Value, class Lock = NullLock,
    class Map = std::unordered_map<
    Key, typename std::list<KeyValuePair<Key, Value> >::iterator> >
    class Cache {
    public:
        typedef KeyValuePair<Key, Value> node_type;
        typedef std::list<KeyValuePair<Key, Value> > list_type;
        typedef Map map_type;
        typedef Lock lock_type;
        using Guard = std::lock_guard<lock_type>;

        /**
         * the max size is the hard limit of keys and (maxSize + elasticity) is the
         * soft limit
         * the cache is allowed to grow till maxSize + elasticity and is pruned back
         * to maxSize keys
         * set maxSize = 0 for an unbounded cache (but in that case, you're better off
         * using a std::unordered_map
         * directly anyway! :)
         */
        explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
        : maxSize_(maxSize), elasticity_(elasticity) {
        }
        virtual ~Cache() = default;

        size_t size() const {
            Guard g(lock_);
            return cache_.size();
        }

        bool empty() const {
            Guard g(lock_);
            return cache_.empty();
        }

        void clear() {
            Guard g(lock_);
            cache_.clear();
            keys_.clear();
        }

        void insert(const Key& k, const Value& v) {
            Guard g(lock_);
            const auto iter = cache_.find(k);
            if (iter != cache_.end()) {
                iter->second->value = v;
                keys_.splice(keys_.begin(), keys_, iter->second);
                return;
            }

            keys_.emplace_front(k, v);
            cache_[k] = keys_.begin();
            prune();
        }

        bool tryGet(const Key& kIn, Value& vOut) {
            Guard g(lock_);
            const auto iter = cache_.find(kIn);
            if (iter == cache_.end()) {
                return false;
            }
            keys_.splice(keys_.begin(), keys_, iter->second);
            vOut = iter->second->value;
            return true;
        }
        
        /**
         *	The const reference returned here is only
         *    guaranteed to be valid till the next insert/delete
         */
        const Value& get(const Key& k) {
            Guard g(lock_);
            const auto iter = cache_.find(k);
            if (iter == cache_.end()) {
                throw KeyNotFound();
            }
            keys_.splice(keys_.begin(), keys_, iter->second);
            return iter->second->value;
        }

        /**
         * returns a copy of the stored object (if found)
         */
        Value getCopy(const Key& k) {
            return get(k);
        }

        bool remove(const Key& k) {
            Guard g(lock_);
            auto iter = cache_.find(k);
            if (iter == cache_.end()) {
                return false;
            }
            keys_.erase(iter->second);
            cache_.erase(iter);
            return true;
        }

        bool contains(const Key& k) {
            Guard g(lock_);
            return cache_.find(k) != cache_.end();
        }

        size_t getMaxSize() const {
            return maxSize_;
        }

        size_t getElasticity() const {
            return elasticity_;
        }

        size_t getMaxAllowedSize() const {
            return maxSize_ + elasticity_;
        }

        template <typename F>
        void cwalk(F& f) const {
            Guard g(lock_);
            std::for_each(keys_.begin(), keys_.end(), f);
        }

    protected:

        size_t prune() {
            size_t maxAllowed = maxSize_ + elasticity_;
            if (maxSize_ == 0 || cache_.size() < maxAllowed) {
                return 0;
            }
            size_t count = 0;
            while (cache_.size() > maxSize_) {
                cache_.erase(keys_.back().key);
                keys_.pop_back();
                ++count;
            }
            return count;
        }

    private:
        // Dissallow copying.
        Cache(const Cache&) = delete;
        Cache& operator=(const Cache&) = delete;

        mutable Lock lock_;
        Map cache_;
        list_type keys_;
        size_t maxSize_;
        size_t elasticity_;
    };

} // namespace LRUCache11
